UVA1218 Perfect Service

一道很不错的树形dp。

令 $dp[u][f]$ 为以$u$为根的子树。

$f=0$，表示$u$为服务器，那么$u$的儿子和父亲既可以是服务器，也可以不是。

$f=1$，表示$u$的父亲为服务器，那么$u$的儿子一定不为服务器。

$f=2$，表示$u$和$u$的父亲均不为服务器，那么$u$的儿子中一定有一个是服务器。

那么转移式为:

$dp[u][0]=\sum_{v \in son_u}min(dp[v][0],dp[v][1])$

$dp[u][1]=\sum_{v \in son_u}dp[v][2]$

$dp[u][2]=min(dp[v_1][2]+dp[v_2][2]+...+dp[v_k][0]+...+dp[v_s][2])$

其中 $s$ 为 $u$ 的子结点个数 ， $k$ 是枚举的为服务器的那个子节点。

这样转移需要$\Theta(n)$ ， 经过观察发现，求和的部分与 $dp[u][1]$ 除了枚举的 $dp[v_k][0]$ 是一致的 ， 于是就可以化简为：

$dp[u][2]=min(dp[ u ][ 2 ] , dp[ u ][ 1 ] - dp[ v ][ 2 ] + dp[ v ][ 0 ])$

最后注意$\text{dp}$的极大值,用 $inf$ 可能会爆 $int$ , 开成 $n+5$ 即可。

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 10000;
int n , u , v , dp[ MAXN + 5 ][ 3 ];


vector< int > Graph[ MAXN + 5 ];

void dfs( int u , int fa ) {
    dp[ u ][ 0 ] = 1; dp[ u ][ 1 ] = 0;
    for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( v == fa ) continue;
        dfs( v , u );

        dp[ u ][ 0 ] += min( dp[ v ][ 0 ] , dp[ v ][ 1 ] );
        dp[ u ][ 1 ] += dp[ v ][ 2 ];
        dp[ u ][ 2 ] = min( dp[ u ][ 2 ] , dp[ u ][ 1 ] - dp[ v ][ 2 ] + dp[ v ][ 0 ] ); 
    }
}

int main( ) {
    while( scanf("%d",&n) ) {
        for( int i = 1 ; i <= n ; i ++ ) {
            Graph[ i ].clear( );
            dp[ i ][ 0 ] = dp[ i ][ 1 ] = dp[ i ][ 2 ] = MAXN;
        }

        for( int i = 1 ; i <= n - 1 ; i ++ ) {
            scanf("%d %d",&u,&v);
            Graph[ u ].push_back( v );
            Graph[ v ].push_back( u );
        }
        
        dfs( 1 , 0 );
        printf("%d\n", min( dp[ 1 ][ 0 ] , dp[ 1 ][ 2 ] ) );

        scanf("%d",&n);
        if( n == -1 ) break;
    }
    return 0;
}